// https://www.lintcode.com/problem/count-and-say/

public class Solution {
    /**
     * @param n: the nth
     * @return: the nth sequence
     */
    public String countAndSay(int n) {
        // write your code here
        if (1 == n) {
            return "1";
        }
        StringBuilder sb = new StringBuilder();
        String prev = countAndSay(n - 1);
        int i = 0;
        while (i < prev.length()) {
            char ch = prev.charAt(i);
            int sum = 1, j = i + 1;
            while (j < prev.length()) {
                if (prev.charAt(i) == prev.charAt(j)) {
                    ++sum;
                    ++j;
                }
                else {
                    break;
                }
            }
            sb.append(sum);
            sb.append(ch);
            i = j;
        }
        return sb.toString();
    }
}